package P3排序算法;

import java.util.Arrays;
import java.util.Set;
import java.util.TreeMap;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {1, 1, 8, 8, 7, 7, 2, 2, 3};
//        countingSort(arr);
//        System.out.println(Arrays.toString(arr));
        countingSortUpper(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void countingSortUpper(int[] arr) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        //O(N)  O(NlogM)
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            //O(logM)
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Set<Integer> set = map.keySet();
        int k = 0;
        //O(M)   O(MlogM)
        for (Integer num : set) {
            //O(logM)
            while (map.get(num) != 0) {
                arr[k++] = num;
                map.put(num, map.get(num) - 1);
            }
        }
    }

    public static void countingSort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        //O(n)
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int[] counts = new int[max - min + 1];
        //O(n)
        for (int i = 0; i < arr.length; i++) {
            counts[arr[i] - min]++;
        }
        int k = 0;
        //O(m + n)
        for (int index = 0; index < counts.length; index++) {
            while (counts[index] != 0) {
                arr[k++] = index + min;
                counts[index]--;
            }
        }
    }
}